package 二叉树的前序遍历;

import java.util.ArrayList;
import java.util.Stack;

public class Solution
{
    public ArrayList<Integer> preorderTraversal (TreeNode root)
    {
        //递归方法
        ArrayList<Integer> integers = new ArrayList<>();
        preorderTraversal(root,integers);
        return integers;
    }
    public void preorderTraversal (TreeNode root,ArrayList<Integer> integers)
    {
        if (root!=null)
        {
            integers.add(root.val);
            preorderTraversal(root.left,integers);
            preorderTraversal(root.right,integers);

        }
    }
    public ArrayList<Integer> preorderTraversal1 (TreeNode root)
    {
        //遍历方法
        //用栈的方式
        ArrayList<Integer> integers = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root==null)
            return integers;
        stack.push(root);
        while (!stack.isEmpty())
        {
            TreeNode node=stack.pop();
            integers.add(node.val);
            if (node.right!=null)
                stack.push(node.right);
            if (node.left!=null)
                stack.push(node.left);
        }
        return integers;
    }
}
